/**
 * 147. 对链表进行插入排序
 * https://leetcode-cn.com/problems/insertion-sort-list/
 */
public class Solutions_147 {
    public static void main(String[] args) {
//        int[] arr = {4, 2, 1, 3};  // output: {1, 2, 3, 4}
        int[] arr = {-1, 5, 3, 4, 0};  // output: {-1, 0, 3, 4, 5}

        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);
        ListNode result = insertionSortList(head);
        System.out.println(MyLinkedListUtils.ListNodeToString(result));
    }

    /**
     * 解法二：插入排序优化版（3ms）
     */
    public static ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            // 保证 head 中存在两个以上的结点，无法排序无意义
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // prev，前一结点，利用前部分链表有序的特点，那么 prev 结点值就是有序链表中最大值，要插入的结点先与 prev 比较，是否是插入还是链接
        ListNode prev = head;
        // cur，进行插入的结点
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val >= prev.val) {
                // 出现最大值，最大值直接链接到有序链表末尾，同时将最大值结点设置为 prev
                prev = cur;
                cur = cur.next;
            } else {
                ListNode temp = dummy;
                while (temp.next.val <= cur.val) {
                    // 移动 cur，直到大于等于 temp.next
                    temp = temp.next;
                }
                prev.next = cur.next;
                // 插入操作
                cur.next = temp.next;
                temp.next = cur;
                // 比较的下一元素
                cur = prev.next;
            }
        }
        return dummy.next;
    }

    /**
     * 解法一：插入排序（22ms）
     * @param head
     * @return
     */
    public static ListNode insertionSortList2(ListNode head) {
        if (head == null || head.next == null) {
            // 没有结点或者只有一个结点的情况，不需要排序
            return head;
        }
        // 建立虚拟头结点
        ListNode dummy = new ListNode(-1);
        // 第一个结点，链接到 dummy 后面，然后将第一个结点与后面的结点断链
        dummy.next = head;
        ListNode temp = head.next;
        head.next = null;

        ListNode pre;
        // 随后遍历头结点后面的链表，对每个结点都进行插入到有序链表 dummy.next 中
        ListNode cur = temp;
        while (cur != null) {
            // 每次都从有序链表 dummy 开始向后遍历
            pre = dummy;
            // 先记录下当前遍历结点的后续链表，再进行断链
            temp = cur.next;
            cur.next = null;

            while (pre.next != null && cur.val > pre.next.val) {
                // 从头开始遍历 pre 链表，当 cur.val 大于遍历的链表结点值时，进入循环
                // 即插入的位置，需要后移
                // 正确位置：pre.val < cur.val < pre.next.val
                pre = pre.next;
            }
            // 插入结点操作
            cur.next = pre.next;
            pre.next = cur;
            // 继续遍历以 temp 为头结点的链表
            cur = temp;
        }
        return dummy.next;
    }
}
